#include<iostream>
#include<vector>
using namespace std;

int uniquePaths(int m, int n){
    //状态表示 dp[i][j]表示以[i,j]为结尾 到达该位置的路径总数
    vector<vector<int>> dp;
    //resize函数扩容时默认值为0
    dp.resize(m + 1, vector<int>(n + 1));

    //初始化
    dp[1][1] = 1;

    //填表顺序
    for (int i = 1; i <= m; i++){
        for (int j = 1; j <= n; j++){
            if (i == 1 && j == 1){
                continue;
            }

            //状态转移方程
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
    }

    //返回值
    return dp[m][n];
}

//63.不同路径2
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid){
    int m = obstacleGrid.size(), n = obstacleGrid[0].size();

    //状态表示，dp[i][j]表示以[i,j]为结尾，到达该位置的路径总数,起点从[1,1]开始
    vector<vector<int>> dp(m + 1, vector<int>(n + 1));

    //初始化
    dp[0][1] = 1;
    //填表
    for (int i = 1; i <= m; i++){
        for (int j = 1; j <= n; j++){
            //判断当前位置是否是障碍
            if(obstacleGrid[i-1][j-1]==1){
                dp[i][j] = 0;
            }
            else{
                //状态转移方程
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
    }

    //返回值
    return dp[m][n];
}

//LCR.166珠宝的最高价值
int jewelleryValue(vector<vector<int>>& frame){
    int m = frame.size(), n = frame[0].size();

    //状态表示 以[i,j]为结尾 dp[i][j]表示到达[i,j]位置时的最高价值 起点从[1,1]开始
    vector<vector<int>> dp(m + 1, vector<int>(n + 1));

    //填表
    for (int i = 1; i <= m; i++){
        for (int j = 1; j <= n; j++){
            //状态转移方程
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + frame[i - 1][j - 1];
        }
    }

    //返回值
    return dp[m][n];
}


//931.下降路径的最小和
int minFallingPathSum(vector<vector<int>>& matrix){
    int m = matrix.size(), n = matrix[0].size();

    //状态表示，以[i,j]为结尾，dp[i][j]表示到达[i,j]位置时的下降路径最小和 起点是下标为1的行
    //学到个新的点，二维数组指定值初始化
    vector<vector<int>> dp(m + 1, vector<int>(n + 2, INT_MAX));

    //初始化
    for (int j = 0; j <= n + 1; j++){
        dp[0][j] = 0;
    }

    //填表
    for (int i = 1; i <= m; i++){
        for (int j = 1; j <= n; j++){
            //状态转移方程
            dp[i][j] = min(min(dp[i - 1][j - 1], dp[i - 1][j]), dp[i - 1][j + 1]) + matrix[i - 1][j - 1];
        }
    }

    //返回值，从状态表最后一行中找到最小的和
    int ret = INT_MAX;
    for (int j = 1; j <= n; j++){
        ret = min(ret, dp[m][j]);
    }

    return ret;
}

//64.最小路径和
int minPathSum(vector<vector<int>>& grid){
    int m = grid.size(), n = grid[0].size();

    //状态表示，以[i,j]为结尾，dp[i][j]表示到达[i,j]位置时的最小路径和，起点从[1,1]开始
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX));

    //初始化
    dp[0][1] = 0;

    //填表
    for (int i = 1; i <= m; i++){
        for (int j = 1; j <= n; j++){
            //状态转移方程
            dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1];
        }
    }

    //返回值
    return dp[m][n];
}



//174.地下城游戏
int calculateMinimumHP(vector<vector<int>>& dungeon){
    int m = dungeon.size(), n = dungeon[0].size();

    //状态表示，以[i,j]为起点，dp[i][j]表示到达终点时需要的最小健康值，终点为[m-1,n-1]
    //由后状态推出前状态
    vector<vector<int>> dp(m + 1, vector<int>(n + 1,INT_MAX));

    //初始化
    dp[m][n - 1] = 1;

    //填表
    for (int i = m - 1; i >= 0; i--){
        for (int j = n - 1; j >= 0; j--){
            //状态转移方程
            dp[i][j] = min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j];
            if(dp[i][j]<=0){
                dp[i][j] = max(1, dp[i][j]);
            }
        }
    }

    //返回值
    return dp[0][0];
}

int main(){

    return 0;
}